Level Generation
Monster Spawning Monsters are generated in packages called 'hordes'. A horde is a monster and allies that may spawn with it (or it may have none) - for instance, the 'vampire bat' horde spawns a vampire bat, then 0-2 vampire bat allies at random. Deeper depths are characterized by new monsters but also by new, larger hordes. When a level is first created, 6 hordes are spawned asleep outside of the upstairs' FOV (unless you are deeper than the amulet - then it increases by 1 per level to 20.). 'Captive' monsters will be picked by this initial spawn - the only thing it doesn't place are 'machine only' hordes (captives without captors, bosses, statued monsters...) Every 125-175 turns, a new horde is spawned on your current level awake. Periodically spawned hordes will never spawn in your FOV, within 15 king's moves of you or inside of 'machines', which is where key/door puzzles and boss fights are hosted. The tile it chooses must also be devoid of liquids and be open floor, so no periodic eel spawns or spawns on doors. Finally, immobile monsters cannot be periodically spawned. If a horde places multiple monsters, they are all 'allies'. This means that if one is alerted to your location, they all will be, making sneaking up on them difficult. Depth Starting at level 2, 10% of hordes are generated 'out of depth'. This means they're picked as though they spawned 1dK levels lower where K = min(depth / 2, 5) (allowing ogres, being 'min depth 7', to spawn on depth 5). Until you go below depth 26, however, hordes deeper than depth 26 will not be picked. (The post-amulet depths feature hordes such as dragon packs and revenant+tentacle horror packs.) Level Profiles and Level Specs Certain probabilities about level generation in Brogue are controlled by the level profile chosen. Currently there is only one level profile, as follows: Cave level chance = 33% Cross room chance = 100% (Yes, all rooms are cross rooms - normal rectangles must have been considered too boring :) ) Chance to attempt to place corridor = 80% Door placement chance = 60% Maximum number of rooms = 99 Maximum number of loops = 30 The level spec is also determined before continuing. It seems most aspects about it were designed to change with the depth, but no such functionality is implemented yet. Currently the parameters are as follows: Rooms (the longer dimension of each cross room half) can be 4-20 tiles wide and 3-7 tiles high. Cross rooms (the shorter dimension of each cross room half) can be 3-12 tiles wide, and 2-5 tiles high. Corridors can be 5 to 15 tiles horizontally, or 2 to 10 tiles vertically. Doors are made secret (depth-1)*67/25 % of the time (rounded down), clamped in the range 0-67%. The number of traps is random between (depth-1)/4 to (depth-1)/2 inclusive. Digging the Level The level starts by randomly placing the first room - if this is the first level of the dungeon, it is always made as a cross room with an upside-down T shape on the bottom center of the map - one rectangle 9x10, the other 20x4. (Measure it - it's always true.) Else, there's a 33% chance of the first room being a cave (see Cave Levels) Else, the first room is a boring rectangle - 4-25 width, 2-7 height, placed randomly on the level. Now, we make 600 attempts (or until we have 99 rooms) to build off of currently existing rooms. Each of those 600 attempts, we pick a direction at random and 80% try to make a corridor with a room at the end 20% try to make a new room (except for the last 225 attempts which are always attempts to make new rooms) After we pick our direction, we pick a random wall that would allow us to build in that direction (from a cave, corridor or room) and attempt 15 times to build a room (or corridor + room) in that direction, choosing lengths, cross lengths and corridor lengths at random within the level spec's ranges. If it worked, we update various structures about how many rooms exist, which rooms connect to which, what walls point where, etc. We also connect it via a door with 60% chance. The next step is to add loops so our tree-structure dungeon has places suitable for pillar dancing and monkeys endlessly running away from you ;) 500 attempts are made or until we have 30 loops. We pick a direction to loop in, pick a random wall and look at the tiles one to either side of it. If they both exist in different rooms, are both floor and are further than 2 rooms apart via shortest path, the wall is hollowed out and turned into a doorway. Thus, loops are only added to rooms that were already adjacent but not connected closely. Next, we add lakes (see the Lakes section) Next, we run autoGenerators, which goes through the autoGeneratorCatalogue looking for entries that satisfy the current depth. This includes terrain (grass, luminscent foilage, fungus forest, bones...), statues, torches, traps, sunlight, darkness, steam vents and machines which build themselves (swamp, idyll, remnant, dismal, bridge turret, lake path turret, trick statue, sentinel, worms in the walls). Connectivity is checked - meaning, for example, traps will never make part of a level inaccessible. If it picked a 'machine', it goes to buildAMachine which does a whole bunch of stuff probably machine specific that I haven't read yet :) Next, we remove diagonal openings. It scans the map for blocks of passable/unpassable terrain in the shapes of 10 01 01 10 and randomly makes one of the two walls floor (or liquid, if it was next to a liquid/chasm) Next, we analyze the map, finding and building a map of all loops and chokepoints. Next, we add treasure machines. Treasure machines are generated at depths 3, 7, 11, 15, 19 and 23. When we generate one, there's a 20% chance of generating a second (then a 20% chance of generating a third, etc) which will mean more machines now but future treasure machines will not spawn until the game catches up (Expect 6 treasure machines unless you get two in depth 23.) buildAMachine is then called to place it. A treasure machine has two components, which will be mixed and matched randomly: Next, we knock down the boundaries between similar lakes where possible. I think what this does is destroy 1 tile thin walls when it detects lakes (also chasms!) are on both sides of it. Next, we build bridges until we can't find nice places to build them. Because this is done after making the level all connected otherwise, burning down bridges will never strand you. Next, we remove orphaned doors and upgrade some doors to secret doors. Orphaned doors are at a T-intersection or a more open area than that or at a dead end or encased in wall, and since that's a weird place for a door to be they'll be removed. Finally, doors are made secret doors with (depth-1)*67/25 % chance clamped to 0-67%. Finally, we make all unexposed walls granite and all exposed walls non-granite. That's all for digging - the rest of the level population (monsters, items, staircases) is handed elsewhere. Lakes In Brogue, lakes, chasms, pools of lava and brimstone are all called 'lakes' and generated the same way - via a cellular automata. A buffer as big as the level is used, and seeded with 55% alive elements and 45% dead elements. 5 iterations are made of the rule B5678/S45678: If I am dead and have 5-8 alive neighbours, I become alive. If I am alive and have 4-8 alive neighbours, I stay alive, else I become dead. After this, every 'blob' of horizontally/vertically connected alive elements is counted, and the largest blob smaller than lakeMaxWidth and lakeMaxHeight is preserved. If no blob is made larger than 4x4 and smaller than this, the cellular automata is started over. lakeMaxWidth/Height start at 30x15 and decrease by 2x1 until 20x10, for 10 different lakes in total. Each lake, once generated, is attempted to be placed - if its placement would block passability from some room to another, the game tries again and gives up after 10 tries. As a result, between 0 and 10 lakes are placed on the map. After placing our lakes, a random liquid type is chosen per lake - lava cannot appear before depth 4, and brimstone cannot appear before depth 18. Then, the lake(s) is(are) placed on the map, surrounded by a 'wreath' of the shallower version of the liquid (1 for chasms, 2 for water and brimstone). If you're interested in how cellular automata work, try MCell: http://www.mirekw.com/ca/index.html Cave Levels Caves are generated similarly to lakes, except with a B678/S45678 rule, and a minimum blob width and height of 50x20, and a max size of the level minus its boundaries. It is then randomly placed on the level as floor and surrounded by walls. This cave, however large or small it may be, is designated the first room and new rooms/corridors are built off of it as normal. Category:Mechanics